﻿#pragma once
#include<string>
#include<vector>
#include<utility>
#include<iostream>
using std::vector;
using std::string;
using std::pair;
using std::cout;
using std::endl;


// 哈希函数采用除留余数法﻿
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
namespace open_address
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv)
		{
			//扩容的问题
			if (_n * 100 / _tables.size() == 70)
			{
				HashTable newHashTable;
				newHashTable._tables.resize(_tables.size() * 2);//“扩容”

				for (size_t i = 0; i < _tables.size(); ++i)//转移数据
				{
					if ((_tables[i])._state == EXIST)
					{
						newHashTable.Insert((_tables[i])._kv);
					}
				}

				//交换对象
				std::swap(newHashTable, *this);
			}

			//插入新数据
			size_t hashi = Hash()(kv.first) % 10;
			if ((_tables[hashi])._kv.first != kv.first)//关键码值唯一性要求
			{
				while ((_tables[hashi])._state == EXIST) // DELETE and EMPTY 对 insert 都是一样的
				{
					++hashi;
					hashi %= _tables.size();
				}

				(_tables[hashi])._kv = kv;
				(_tables[hashi])._state = EXIST;
				++_n;
				return true;
			}
			return false;
		}

		HashData<K, V>* Find(const K& key)
		{
			size_t hashi = Hash()(key) % 10;
			if (_tables[hashi]._state == EMPTY)
			{
				cout << "未查找到该数据" << endl;
				return nullptr;
			}
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._kv.first == key)
				{
					//cout << "查找成功" << endl;
					return &_tables[hashi];
				}
				++hashi;
			}
			cout << "查找的目标不存在" << endl;
			return nullptr;
		}
		bool Erase(const K& key)
		{
			HashData<K, V>* pointer = Find(key);
			if (!pointer)
			{
				cout << "要删除的目标不存在" << endl;
				return false;
			}

			pointer->_state = DELETE;
			return true;
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;  // 表中存储数据个数
	};

	//////////////////////////////////////TEST///////////////////////////////////////////
	void test_int()
	{
		HashTable<int, int> hashT;
		hashT.Insert(std::make_pair(1, 1));
		hashT.Insert(std::make_pair(2, 1));
		hashT.Insert(std::make_pair(4, 1));
		hashT.Insert(std::make_pair(6, 1));
		hashT.Insert(std::make_pair(9, 1));
		hashT.Insert(std::make_pair(22, 1));
		hashT.Insert(std::make_pair(13, 1));
		hashT.Insert(std::make_pair(3, 1));

		//cout << "find 1 :" << hashT.Find(1) << endl;
		//cout << "find 2 :" << hashT.Find(2) << endl;
		//cout << "find 3 :" << hashT.Find(3) << endl;
		//cout << "find 4 :" << hashT.Find(4) << endl;
		//cout << "find 99 :" << hashT.Find(99) << endl;

		hashT.Find(2);
		hashT.Find(3);
		hashT.Find(4);
		hashT.Find(99);

		cout << "-----------------Erase Test-----------------" << endl;

		hashT.Erase(9);
		hashT.Insert(std::make_pair(99,2));
		hashT.Find(99);
	}

	void test_string()
	{
		HashTable<string, string> hashT;
		hashT.Insert(std::make_pair("what", "何"));
		hashT.Insert(std::make_pair("make", "使得"));
		hashT.Insert(std::make_pair("Florida", "佛罗里达"));
		hashT.Insert(std::make_pair("get", "得到"));
		hashT.Insert(std::make_pair("virtual", "虚拟的"));
		hashT.Insert(std::make_pair("plain", "朴素的"));
		hashT.Insert(std::make_pair("red", "红色"));


		//cout << "find 1 :" << hashT.Find(1) << endl;
		//cout << "find 2 :" << hashT.Find(2) << endl;
		//cout << "find 3 :" << hashT.Find(3) << endl;
		//cout << "find 4 :" << hashT.Find(4) << endl;
		//cout << "find 99 :" << hashT.Find(99) << endl;

		hashT.Find("made");
		hashT.Find("whet");
		hashT.Find("red");
		hashT.Find("Florida");
		hashT.Find("give");
		hashT.Find("get");

	}


}

// 实现完成后，请对整形 和 字符串完成测试